package sort.test147;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/19 9:34
 */
public class Solution1 {

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode b = head;
        while (b.next != null) {
            if (b.val < b.next.val) {
                b = b.next;
            } else {
                ListNode c = b.next;
                b.next = b.next.next;
                c.next = null;
                ListNode d = dummy;
                while (c.val > d.next.val) {
                    d = d.next;
                }
                c.next = d.next;
                d.next = c;
            }
        }
        return dummy.next;
    }
}
